Visual Basic Source Code/Visual Basic Source Code.iso/vbsource/vbdatabs/tree.cpp

C/C++ Source or Header | 1999-03-17 | 12KB | 456 lines

// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Source Code File Name: tree.cpp
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced by: Doug Gaer
// File Creation Date: 11/07/1996
// Date Last Modified: 03/17/1999
// ----------------------------------------------------------- //
// ------------- Program description and details ------------- //
// ----------------------------------------------------------- //
/*
THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

This is a simple class implementation of a binary search tree
used to create a tree of character strings. The char * data type
in the TreeNode class is used as a pointer to a pre-allocated
strings. The tree structure itself stores a hierarchal collection
of nodes. Each node stores a pointer to a unique character string
along with left and right pointers to other nodes in the tree.
*/
// ----------------------------------------------------------- //
#include <iostream.h>
#include <string.h>

class Tnode; // Forward class name

// VisitFunc is a pointer to void(Tnode *Node) that points to
// a visit function used to process node data during tree traversals
typedef void (*VisitFunc)(Tnode *Node);

// (T)ree (N)ode base class
class Tnode
{
public:
  Tnode() { right = left = 0; data = 0; }
  Tnode(char *key, Tnode *l = 0, Tnode *r = 0) {
    data = strdup(key); left = l; right = r;
  }

public:
  char *data;   // data for this tree
  Tnode *right; // subtree to the right
  Tnode *left;  // subtree to the left
};

// Binary Search (T)ree class
class Tree : public Tnode
{
public:
  Tree() { root = 0; }
  ~Tree() { Clear(); }
  Tree(const Tree &t) { this->Copy(t); }
  void operator=(const Tree &t) { this->Copy(t); }

public:
  int Add(char *key);
  int Remove(char *key);
  int Find(char *key);
  void Clear();
  int Copy(const Tree &t);
  void PrintTree(VisitFunc Visit) { PrintInOrder(root, Visit); }
  int GetHeight() { return Height(root); }

private: // Functions for internal processing only
  Tnode *SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side);
  Tnode *Insert(Tnode *&root, char *key, int &exists);
  Tnode *DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side);
  Tnode *GetParentOfSuccessor(Tnode *node);
  Tnode *Detach(Tnode *&root, char *key);
  int Delete(Tnode *&root, char *key);
  void PrintInOrder(Tnode *tree, VisitFunc Visit);
  void DeleteTree(Tnode *t);
  Tnode *DupTree(Tnode *t);
  int Height(Tnode *t);

private:
  Tnode *root; // Pointer to the top of the tree
};

int Tree::Add(char *key)
// Add an entry to the tree.
{
  int exists;
  Insert(root, key, exists);
  return exists == 0; // Return true if the key did not already exist
}

int Tree::Remove(char *key)
// Remove a node from the tree.
// Returns zero if the node does not exist.
{
  return Delete(root, key);
}

void Tree::Clear()
// Clear the tree.
{
  DeleteTree(root);
  root = 0;
}

int Tree::Find(char *key)
// Search the tree for matching entry
{
  Tnode *parent;
  int side;

  // Search the tree
  Tnode *node = SearchForParent(root, key, parent, side);

  return node != 0; // Return true if the matching node is found
}

int Tree::Copy(const Tree &t)
// Copy tree t into the tree object that invoked the call.
{
  Clear();
  Tnode *r = DupTree(t.root);

  if(r) {
    root = r; // Tree was copied from the bottom up
    return 1;
  }
  return 0; // Tree was not copied
}

Tnode *Tree::Insert(Tnode *&root, char *key, int &exists)
// Insert a new node into the tree. Returns the matching node,
// new or old and may modify the root pointer.
{
  Tnode *parent;
  int side;

  // Look for a place to insert the node
  Tnode *node = SearchForParent(root, key, parent, side);

  if(node == 0) { // Node does not exist in the tree
    node = new Tnode(key);
    if(parent) {
      if(side) parent->right = node; else parent->left = node;
    }
    else // No parent, so this is the new root
      root = node;

    exists = 0;
  }
  else
    exists = 1;

  return node;
}

Tnode *Tree::SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side)
// Returns the parent of the matching node, as well as the node itself.
// Each node to the left is smaller then the given node, and each node
// to right is larger.
{
  parent = 0;
  while(node) {
    if(strcmp(key, node->data) == 0) break;
    parent = node;
    if(strcmp(key, node->data) < 0) { // Node is smaller
      side = 0;
      node = node->left;
    }
    else { // Node is larger
      side = 1;
      node = node->right;
    }
  }
  return node;
}

Tnode *Tree::DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side)
// Detach the node with parent from the tree. The node is the left
// child if side equals zero or right child if side equals one.
// Returns a pointer to the node.
{
  Tnode *psucc; // Parent of successor
  Tnode *replacement;

  if(node) {
    if(node->left == 0 || node->right == 0) {
      // At lease one child is null, so use the other as the replacement
      replacement = (node->left) ? node->left : node->right;
    }
    else { // Neither child is null
      psucc = GetParentOfSuccessor(node); // Guaranteed not to be null
      if(psucc == node) { // Immediate successor
    replacement = psucc->right;
      }
      else {
    // Detach replacement from its current loaction and
        // relocate it to where node used to be
    replacement = psucc->left;
    psucc->left = psucc->left->right;
        replacement->right = node->right;
      }

      // Finish reloacting replacement to where node used to be
      replacement->left = node->left;
    }

    if(parent) { // Fix parent of node to point to replacement
      if(side)
        parent->right = replacement; else parent->left = replacement;
    }
    else root = replacement; // No parent, so node was the root
  }
  return node;
}

Tnode *Tree::GetParentOfSuccessor(Tnode *node)
// Used by the Tree::DetachNode() function to find the parent of
// the successor node. Returns zero if no successor is found.
{
  Tnode *parent = 0;

  // Go right once, then all the way to the left
  Tnode *q = node->right;
  if(q) {
    parent = node;
    while(q->left) {
      parent = q;
      q = q->left;
    }
  }
  return parent;
}

Tnode *Tree::Detach(Tnode *&root, char *key)
// Detaches the node matching key from the tree.
{
  int side;
  Tnode *parent, *node;
  node = SearchForParent(root, key, parent, side);
  return DetachNode(root, node, parent, side);
}

int Tree::Delete(Tnode *&root, char *key)
// Deletes the node from the tree.
// Returns zero if the node does not exist.
{
  Tnode *node = Detach(root, key);
  delete node;
  return node != 0;
}

void Tree::DeleteTree(Tnode *t)
// Recursive function used to clear the tree from the bottom up.
{
  if(t == 0) return;
  if(t->left == 0) return; else DeleteTree(t->left);
  if(t->right == 0) return; else DeleteTree(t->right);
  delete t;
}

void Tree::PrintInOrder(Tnode *tree, VisitFunc Visit)
// Visit each node of tree Tree in in-order, (first the Left
// subtree, then the parent, then the Right subtree), with
// tail recursion removed
{
  while(tree) {
    PrintInOrder(tree->left, Visit);
    Visit(tree);
    tree = tree->right;
  }
}

Tnode *Tree::DupTree(Tnode *t)
// Recursive function that to duplicates a tree using
// postorder traversal.
{
  if(t == 0) return 0;
  Tnode *l = DupTree(t->left);
  Tnode *r = DupTree(t->right);
  return new Tnode(t->data, l, r);
}

int Tree::Height(Tnode *t)
// The height of a tree is the maximum of the height of
// its two su